package cn.edu.leetcode.字符串;

import java.util.*;

public class 单词拆分 {
    public static boolean wordBreak(String s, List<String> wordDict) {
        HashMap<Integer, Boolean> map = new HashMap<>();
        return digui(s, wordDict, 0, map);
    }


    public static boolean digui(String s, List<String> wordDict, int i, HashMap<Integer, Boolean> map) {
        if (map.containsKey(i)) return map.get(i);
        if (i == s.length()) return true;

        for (String word : wordDict) {
            if (i + word.length() <= s.length() && s.startsWith(word, i)) {

                if (digui(s, wordDict, i + word.length(), map)) return true;
            }
        }

        map.put(i, false);
        return false;
    }

    public static void main(String[] args) {
        String s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
        List<String> wordDict = Arrays.asList("a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa");

        System.out.println(wordBreak(s, wordDict));
    }
}
